package RelUtilityClasses;

import java.io.Serializable;
import java.util.*;

import PrimitiveDataStructures.PrimitiveDS;

/**
 * 
 * A class that represents a decomposition graph.
 * 
 * @author Yevgeny Levanzov & Daniel Samuelov
 * 
 */
public class DecompositionGraph implements Iterable<DecompositionGraph.Vertex>, Serializable {

	private List<Vertex> vertices;
	
	private boolean topSorted;
	
	private boolean cycleInGraph;   //for semantic checks.
	
	private static final long serialVersionUID = 42L; /* impl. serializable. */
	
	/**
	 * Default constructor.
	 * 
	 */
	public DecompositionGraph() {

		this.vertices = new ArrayList<Vertex>();
		this.topSorted = false;
		this.cycleInGraph = false;
	}

	/**
	 * Adds vertex to graph.
	 * 
	 * @param v the vertex to add
	 */
	public void addVertex(Vertex v) {

		this.vertices.add(v);
	}
	
	
	/**
	 * 
	 * Returns Vertex object of a vertex in this graph, by given name,
	 * or null if not found. 
	 * 
	 * @param name the name of vertex 
	 * 
	 * @return Vertex object of a vertex in this graph, by given name,
	 * 		   or null if not found. 
	 */
	public Vertex getVertexByName(String name) {

		for(Vertex v : vertices) {
			
			if (v.getName().equals(name)) {
				return v;
			}
		}
		
		return null;
	}
	
	
	
	/* 
	 * Returns iterator over vertices in topological order. 
	 * 
	 * (non-Javadoc)
	 * @see java.lang.Iterable#iterator()
	 */
	public Iterator<Vertex> iterator() {
		
		if (!topSorted) {
			topologicalSort();
			topSorted = true;
		}
		
		if (this.cycleInGraph) {  //graph isn't DAG - no topo. order - return null.
			return null;
		}
		
		return vertices.iterator();
	}
	
	
	//sorts vertices list topologically.
	private void topologicalSort() {
		
        List<Vertex> lst = new ArrayList<Vertex>();
        
        DFS(lst);  //lst returns sorted in topo. order.
        
        vertices.clear();
        
        vertices.addAll(lst);
	}
	
	
	//the DFS algorithm main function.
	private void DFS(List<Vertex> topsortList) {
		
		for (Vertex v : vertices) {   //init.
			v.setColor("WHITE");
		}
			
		for (Vertex v : vertices) {

			if (v.getColor().equals("WHITE")) {
				DFSVisit(v, topsortList);
			}
		}

	}
	
	
	//the DFS algorithm recursive visit method.
	private void DFSVisit(Vertex v, List<Vertex> topsortList) {
		
		v.setColor("GRAY");
		
		List<Edge> edges = v.getAdjList();
		
		for (Edge e : edges) {  //going through all neighbors.
			
			Vertex dest = getVertexByName(e.getDestVertName());
			
			if (dest.getColor().equals("WHITE")) {
				DFSVisit(dest, topsortList);
			}
			
			if (dest.getColor().equals("GRAY")) {  //back edge - not SAG.
				this.cycleInGraph = true;
				return;
			}

		}
		
		v.setColor("BLACK");
		
		topsortList.add(0, v);  //building the topo. order list.
	}
	
	

	/* 
	 * (non-Javadoc)
	 * @see java.lang.Object#toString()
	 */
	@Override
	public String toString() {
			
		return vertices.toString();		
	}

	
	/**
	 * 
	 * A class for a vertex of decomposition graph. 
	 * 
	 * @author Yevgeny Levanzov & Daniel Samuelov
	 * 
	 */
	public static class Vertex implements Serializable {

		private String name;

		//names of columns of sink vertex (out-degree = 0).
		private List<String> sinkColsNames;
		
		private List<Edge> adjacent;
		
		//for DFS.
		private String color;
		
		//for remove and update operations.
		private List<String> boundCols;
		private boolean aboveCut;

		private static final long serialVersionUID = 41L; /* impl. serializable. */
		
		/**
		 * A constructor.
		 * 
		 * @param name the name of the vertex
		 */
		public Vertex(String name) {

			this.name = name;
			this.sinkColsNames = new ArrayList<String>();
			
			adjacent = new ArrayList<Edge>();
			
			boundCols = new ArrayList<String>();
			
			aboveCut = false;
		}

		
		/**
		 * Getter of sink columns names.
		 * 
		 * @return sink columns names
		 */
		public List<String> getSinkColsNames() {

			return this.sinkColsNames;
		}
		
		/**
		 * Setter for sink columns names.
		 * 
		 * @param s the list of names to set
		 * 
		 */
		public void setSinkColsNames(List<String> s) {

			this.sinkColsNames.addAll(s);
			Collections.sort(this.sinkColsNames);
		}
		
		/**
		 * Returns true iff this vertex is a sink.
		 * 
		 * @return true iff this vertex is a sink
		 */
		public boolean isSinkVertex() {

			return (!this.sinkColsNames.isEmpty());
		}
		
		/**
		 * Getter for vertex name.
		 * 
		 * @return vertex name
		 */
		public String getName() {

			return this.name;
		}
		


		/**
		 * Getter for vertex adj. list.
		 * 
		 * @return vertex adj. list
		 */
		public List<Edge> getAdjList() {

			return this.adjacent;
		}

		
		/** 
		 * Adds adj. edge to this vertex.
		 * 
		 * @param e the edge to add
		 */
		public void addAdj(Edge e) {

			this.adjacent.add(e);
		}
		
		
		/**
		 * Setter for DFS color.
		 * 
		 * @param c the color to set
		 */
		public void setColor(String c) {

			this.color = c;
		}
		
		/**
		 * Getter for DFS color.
		 * 
		 * @return the color of the vertex
		 */
		public String getColor() {

			return this.color;
		}
		
		
		/**
		 * Sets columns bound in this vertex. 
		 * 
		 * @param columns the bound columns
		 */
		public void setBoundCols(List<String> cols) {
			
			this.boundCols.clear();
			this.boundCols.addAll(cols);
		}
		
		
		/**
		 * Returns columns bound in this vertex.
		 * 
		 * @return columns bound in this vertex
		 */
		public List<String> getBoundCols() {
			
			return this.boundCols;
		}
		
		
		/**
		 * Sets whether vertex is above or below the cut (for remove/update). 
		 * 
		 * @param b the flag to set
		 */
		public void setAboveCut(boolean b) {
			
			this.aboveCut = b;
		}
		
		/**
		 * Returns whether vertex is above or below the cut (for remove/update). 
		 * 
		 * @return whether vertex is above or below the cut
		 */
		public boolean isAboveCut() {
			
			return this.aboveCut;
		}

		
		/* (non-Javadoc)
		 * @see java.lang.Object#equals(java.lang.Object)
		 */
		@Override
		public boolean equals(Object v) {

			return (this.name.equals(((Vertex)v).getName()));
		}
		
		/* (non-Javadoc)
		 * @see java.lang.Object#toString()
		 */
		@Override
		public String toString() {
			
			String s = name + ": ";
			
			if (!sinkColsNames.isEmpty()) {
				s = s + sinkColsNames;
			} else {
				s = s + adjacent;
			}
			
			s = s + ", Bound Columns: " + boundCols;
					
			return s;		
		}

	} //end of class Vertex.
	
	
	/**
	 * 
	 * A class for an edge of decomposition graph. 
	 * 
	 * @author Yevgeny Levanzov & Daniel Samuelov
	 *
	 */
	public static class Edge implements Serializable {
		
		private String originVertName;
		private String destVertName;

		private List<String> cols;
		private PrimitiveDS ds;
		
		private static final long serialVersionUID = 40L; /* impl. serializable. */

		/**
		 * A constructor. 
		 * 
		 * @param orig name of origin vertex
		 * @param dest name if dest. vertex
		 * @param col list of mapping columns
		 * @param ds the mapping ds
		 * 
		 */
		public Edge(String orig, String dest, List<String> col, PrimitiveDS ds) {

			this.originVertName = orig;
			this.destVertName = dest;

			this.cols = new ArrayList<String>(col);
			Collections.sort(this.cols);
			
			this.ds = ds;
		}

		/**
		 * Getter of origin vertex name.
		 * 
		 * @return origin vertex name
		 */
		public String getOriginVertName() {

			return this.originVertName;
		}

		
		/**
		 * Getter of dest. vertex name.
		 * 
		 * @return dest. vertex name.
		 */
		public String getDestVertName() {

			return this.destVertName;
		}

		/**
		 * Getter of list of mapping columns.
		 * 
		 * @return list of mapping columns
		 */
		public List<String> getCols() {

			return this.cols;
		}

		/**
		 * Getter of mapping ds.
		 * 
		 * @return mapping ds
		 */
		public PrimitiveDS getPrimitiveDS() {

			return this.ds;
		}
		
		/* (non-Javadoc)
		 * @see java.lang.Object#toString()
		 */
		@Override
		public String toString() {
			
			String s = "vert: " + destVertName + " cols: " + cols + " ds: " + ds;
					
			return s;		
		}

	}  //end of class Edge.

}
